/**
 * 102. 二叉树的层序遍历
 *
 * 【中等】
 *
 * 给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
 *
 * 示例 1：
 * 【https://assets.leetcode.com/uploads/2021/02/19/tree1.jpg】
 * 输入：root = [3,9,20,null,null,15,7]
 * 输出：[[3],[9,20],[15,7]]
 *
 * 示例 2：
 * 输入：root = [1]
 * 输出：[[1]]
 *
 * 示例 3：
 * 输入：root = []
 * 输出：[]
 */

import { TreeNode } from '../utils/tree'

// 深度优先 DFS
var levelOrder = function levelOrder(root: TreeNode | null): number[][] {
	if (!root) {
		return []
	}
	const res = []
	const dfs = (root, deep, res) => {
		if (!root) {
			return []
		}
		if (!res[deep]) {
			res[deep] = []
		}

		res[deep].push(root.val)
		dfs(res.left, deep + 1, res)
		dfs(res.right, deep + 1, res)
	}
	dfs(root, 0, res)
	return res
}

// 广度优先 BFS
var levelOrder = function levelOrder(root: TreeNode | null): number[][] {
	if (!root) {
		return []
	}
	const res: number[][] = []
	const queue = [root]
	while (queue.length) {
		const arr: number[] = []
		let len = queue.length
		while (len--) {
			root = queue.shift()!
			arr.push(root.val)
			if (root.left) {
				queue.push(root.left)
			}
			if (root.right) {
				queue.push(root.right)
			}
		}

		res.push(arr)
	}

	return res
}
